Internet Surfer 2.0/Internet Surfer 2.0 (Wayzata Technology) (1996).iso/pc/text/mac/faqs.476

Text File | 1996-02-12 | 28.1 KB | 631 lines

Frequently Asked Questions (FAQS);faqs.476



Ask #2, !"Is #3 an R?".  "No" implies that #3 is a P.  "Yes" implies that #4
is a P.

Having identified someone as a P, there are at most C(5,2)=10 possible
patterns, and hence at most 10*6=60 possible results.  We can determine which
one reflects reality with at most 6 more questions with a binary search.  (At
each step, bisect the set of possible answers, and ask the question !"Is the
correct pattern in the first subset?".)

Now, let's show that it can't be done in 7.

After asking your first two questions, renumber if necessary so that the first
question was directed to #1 and the second to #2.  (If you asked the same
person twice, you're even worse off than in the analysis below.)  You have no
way to rule out the possibility that both are Rs, so pattern RRPPPP yields 6
possibilities.  Of the four patterns RPRPPP RPPRPP RPPPRP RPPPPR, your first
question gave no information and the second had one bit; so at best you can
eliminate half of these 4*6 possibilities, leaving 12.  Similarly for the four
patterns PRRPPP PRPRPP PRPPRP PRPPPR there remain at least 12 possibilities.
Of the remaining 6 patterns PPRRPP PPRPRP PPRPPR PPPRRP PPPRPR PPPPRR, your
two bits of information can eliminate 3/4 of the 6*6, leaving 9.  Thus, after
two questions there are at least 6+12+12+9=39 arrangements that could have
given the answers you heard; your five remaining questions have only 32
possible replies, so you can't distinguish them.

==> logic/smullyan/painted.heads.p <==
While three logicians were sleeping under a tree, a malicious child painted
their heads red.  Upon waking, each logician spies the child's handiwork as
it applied to the heads of the other two.  Naturally they start laughing.
Suddenly one falls silent.  Why?

==> logic/smullyan/painted.heads.s <==
The one who fell silent, presumably the quickest of the three, reasoned
that his head must be painted also.  The argument goes as follows.
Let's call the quick one Q, and the other two D and S.  Let's assume
Q's head is untouched.  Then D is laughing because S's head is painted,
and vice versa.  But eventually, D and S will realize that their head
must be painted, because the other is laughing.  So they will quit
laughing as soon as they realize this.  So, Q waits what he thinks is
a reasonable amount of time for them to figure this out, and when they
don't stop laughing, his worst fears are confirmed.  He concludes that
his assumption is invalid and he must be crowned in crimson too.


==> logic/smullyan/priest.p <==
A priest takes confession of all the inhabitants in a small town.  He
discovers that in N married pairs in the town, one of the pair has
committed adultery.  Assume that the spouse of each adulterer does not
know about the infidelity of his or her spouse, but that, since it is
a small town, everyone knows about everyone else's infidelity.  In
other words, each spouse of an adulterer thinks there are N - 1
adulterers, but everyone else thinks there are N adulterers.  The
priest, who is an Old Testament type, decides that he should do
something about the situation.  He cannot break the confessional, but
being an amateur logician of sorts, he hits upon a plan to do God's
work.  He announces in Mass one Sunday that the spouse of each
adulterer has the moral obligation to punish his or her adulterous
spouse by publicly denouncing them in church, and that he will make
time during his next Sunday service for this, and continue to do so
until all adulterers have been denounced.  Is the priest correct?  Will
this result in every adulterer being denounced?

==> logic/smullyan/priest.s <==
Yes.  Let's start with the simple case that N = 1.  The offended spouse
reasons as follows: the priest knows there is at least one adulterer,
but I don't know who this person is, and I would if it were anyone
other than me, so it must be me.  What happens if N = 2?  On the first
Sunday, the two offended spouses each calmly wait for the other to get
up and condemn their spouses.  When the other doesn't stand, they
think:  They do not think that they are a victim.  But if they do not
think they are victims, then they must think there are no adulterers,
contrary to what the priest said.  But everyone knows the priest speaks
with the authority of God, so it is unthinkable that he is mistaken.
The only remaining possibility is that they think there WAS another
adulterer, and the only possibility is: MY SPOUSE!  So, they know that
they too must be victims.  So on the next Sunday, they will get up.
What if N = 3?  On the first Sunday, each victim waits for the other
two to get up.  When they do not, they assume that they did not get up
because they did not know about the other person (in other words, they
hypothesize that each of the two other victims thought there was only
one adulterer).  However, each victim reasons, the two will now realize
that they must be two victims, for the reasons given under the N = 2
case above.  So they will get up next Sunday.  This excuse lasts until
the next Sunday, when still no one gets up, and now each victim
realizes that either the priest was mistaken (unthinkable!) or there
are really three victims, and I am ONE!  So, on the third Sunday, all
three get up.  This reasoning can be repeated inductively to show that
no one will do anything (except use up N - 1 excuses as to why no one
got up) until the Nth Sunday, when all N victims will arise in unison.

By the way, the rest of the town, which thinks there are N adulterers,
is about to conclude that their perfectly innocent spouses have been
unfaithful too.  This includes the adulterous spouses, who are about to
conclude that the door swings both ways.  So the priest is playing a
dangerous game.  A movie plot in there somewhere?

==> logic/smullyan/stamps.p <==
The moderator takes a set of 8 stamps, 4 red and 4 green, known to the
logicians, and loosely affixes two to the forehead of each logician so that
each logician can see all the other stamps except those 2 in the moderator's
pocket and the two on her own head.  He asks them in turn
if they know the colors of their own stamps:
  A: "No"
  B: "No"
  C: "No"
  A: "No
  B: "Yes"
  What are the colors of her stamps, and what is the situation?

==> logic/smullyan/stamps.s <==
B says: "Suppose I have red-red. A would have said on her
second turn: 'I see that B has red-red. If I also have red-red, then all
four reds would be used, and C would have realized that she had green-green.
But C didn't, so I don't have red-red.  Suppose I have green-green. In that
case, C would have realized that if she had red-red, I would have seen
four reds and I would have answered that I had green-green on my first
turn.  On the other hand, if she also has green-green [we assume that
A can see C; this line is only for completeness], then B would have seen
four greens and she would have answered that she had two reds.  So C would
have realized that, if I have green-green and B has red-red, and if
neither of us answered on our first turn, then she must have green-red.
  "'But she didn't. So I can't have green-green either, and if I can't have
green-green or red-red, then I must have green-red.'
  So B continues: "But she (A) didn't say that she had green-red, so
the supposition that I have red-red must be wrong.  And as my logic applies
to green-green as well, then I must have green-red."
  So B had green-red, and we don't know the distribution of the others
certainly.
  (Actually, it is possible to take the last step first, and deduce
that the person who answered YES must have a solution which would work
if the greens and reds were switched -- red-green.)

==> logic/timezone.p <==
Two people are talking long distance on the phone; one is in an East-
Coast state, the other is in a West-Coast state.  The first asks the other
"What time is it?", hears the answer, and says, "That's funny.  It's the
same time here!"

==> logic/timezone.s <==
One is in Eastern Oregon (in Mountain time), the other in
Western Florida (in Central time), and it's daylight-savings
changeover day at 1:30 AM.

==> logic/unexpected.p <==
Swedish civil defense authorities announced that a civil defense drill would
be held one day the following week, but the actual day would be a surprise.
However, we can prove by induction that the drill cannot be held.  Clearly,
they cannot wait until Friday, since everyone will know it will be held that
day.  But if it cannot be held on Friday, then by induction it cannot be held
on Thursday, Wednesday, or indeed on any day.

What is wrong with this proof?

==> logic/unexpected.s <==
This problem has generated a vast literature (see below).  Several
solutions of the paradox have been proposed, but as with most paradoxes
there is no consensus on which solution is the "right" one.

The earliest writers (O'Connor, Cohen, Alexander) see the announcement as
simply a statement whose utterance refutes itself.  If I tell you that I
will have a surprise birthday party for you and then tell you all the
details, including the exact time and place, then I destroy the surprise,
refuting my statement that the birthday will be a surprise.

Soon, however, it was noticed that the drill could occur (say on Wednesday),
and still be a surprise.  Thus the announcement is vindicated instead of
being refuted.  So a puzzle remains.

One school of thought (Scriven, Shaw, Medlin, Fitch, Windt) interprets
the announcement that the drill is unexpected as saying that the date
of the drill cannot be deduced in advanced.  This begs the question,
deduced from which premises?  Examination of the inductive argument
shows that one of the premises used is the announcement itself, and in
particular the fact that the drill is unexpected.  Thus the word
"unexpected" is defined circularly.  Shaw and Medlin claim that this
circularity is illegitimate and is the source of the paradox.  Fitch
uses Godelian techniques to produce a fully rigorous self-referential
announcement, and shows that the resulting proposition is
self-contradictory.  However, none of these authors explain how it can
be that this illegitimate or self-contradictory announcement
nevertheless appears to be vindicated when the drill occurs.  In other
words, what they have shown is that under one interpretation of "surprise"
the announcement is faulty, but their interpretation does not capture the
intuition that the drill really is a surprise when it occurs and thus
they are open to the charge that they have not captured the essence of
the paradox.

Another school of thought (Quine, Kaplan and Montague, Binkley,
Harrison, Wright and Sudbury, McClelland, Chihara, Sorenson) interprets
"surprise" in terms of "knowing" instead of "deducing."  Quine claims
that the victims of the drill cannot assert that on the eve of the last
day they will "know" that the drill will occur on the next day.  This
blocks the inductive argument from the start, but Quine is not very
explicit in showing what exactly is wrong with our strong intuition
that everybody will "know" on the eve of the last day that the drill
will occur on the following day.  Later writers formalize the paradox
using modal logic (a logic that attempts to represent propositions
about knowing and believing) and suggest that various axioms about
knowing are at fault, e.g., the axiom that if one knows something, then
one knows that one knows it (the "KK axiom").  Sorenson, however,
formulates three ingenious variations of the paradox that are
independent of these doubtful axioms, and suggests instead that the
problem is that the announcement involves a "blindspot":  a statement
that is true but which cannot be known by certain individuals even if
they are presented with the statement.  This idea was foreshadowed by
O'Beirne and Binkley.  Unfortunately, a full discussion of how this
blocks the paradox is beyond the scope of this summary.

Finally, there are two other approaches that deserve mention.  Cargile
interprets the paradox as a game between ideally rational agents and finds
fault with the notion that ideally rational agents will arrive at the same
conclusion independently of the situation they find themselves in.  Olin
interprets the paradox as an issue about justified belief: on the eve of
the last day one cannot be justified in believing BOTH that the drill will
occur on the next day AND that the drill will be a surprise even if both
statements turn out to be true; hence the argument cannot proceed and the
drill can be a surprise even on the last day.

For those who wish to read some of the literature, good papers to start with
are Bennett-Cargile and both papers of Sorenson.  All of these provide
overviews of previous work and point out some errors, and so it's helpful to
read them before reading the original papers.  For further reading on the
"deducibility" side, Shaw, Medlin and Fitch are good representatives.  Other
papers that are definitely worth reading are Quine, Binkley, and Olin.

D. O'Connor, "Pragmatic Paradoxes," Mind 57:358-9, 1948.
L. Cohen, "Mr. O'Connor's 'Pragmatic Paradoxes,'" Mind 59:85-7, 1950.
P. Alexander, "Pragmatic Paradoxes," Mind 59:536-8, 1950.
M. Scriven, "Paradoxical Announcements," Mind 60:403-7, 1951.
D. O'Connor, "Pragmatic Paradoxes and Fugitive Propositions," Mind 60:536-8,
 1951
P. Weiss, "The Prediction Paradox," Mind 61:265ff, 1952.
W. Quine, "On A So-Called Paradox," Mind 62:65-7, 1953.
R. Shaw, "The Paradox of the Unexpected Examination," Mind 67:382-4, 1958.
A. Lyon, "The Prediction Paradox," Mind 68:510-7, 1959.
D. Kaplan and R. Montague, "A Paradox Regained," Notre Dame J Formal Logic
 1:79-90, 1960.
G. Nerlich, "Unexpected Examinations and Unprovable Statements," Mind
 70:503-13, 1961.
M. Gardner, "A New Prediction Paradox," Brit J Phil Sci 13:51, 1962.
K. Popper, "A Comment on the New Prediction Paradox," Brit J Phil Sci 13:51,
 1962.
B. Medlin, "The Unexpected Examination," Am Phil Q 1:66-72, 1964.
F. Fitch, "A Goedelized Formulation of the Prediction Paradox," Am Phil Q
 1:161-4, 1964.
R. Sharpe, "The Unexpected Examination," Mind 74:255, 1965.
J. Chapman & R. Butler, "On Quine's So-Called 'Paradox,'" Mind 74:424-5, 1965.
J. Bennett and J. Cargile, Reviews, J Symb Logic 30:101-3, 1965.
J. Schoenberg, "A Note on the Logical Fallacy in the Paradox of the
 Unexpected Examination," Mind 75:125-7, 1966.
J. Wright, "The Surprise Exam: Prediction on the Last Day Uncertain," Mind
 76:115-7, 1967.
J. Cargile, "The Surprise Test Paradox," J Phil 64:550-63, 1967.
R. Binkley, "The Surprise Examination in Modal Logic," J Phil 65:127-36,
 1968.
C. Harrison, "The Unanticipated Examination in View of Kripke's Semantics
 for Modal Logic," in Philosophical Logic, J. Davis et al (ed.), Dordrecht,
 1969.
P. Windt, "The Liar in the Prediction Paradox," Am Phil Q 10:65-8, 1973.
A. Ayer, "On a Supposed Antinomy," Mind 82:125-6, 1973.
M. Edman, "The Prediction Paradox," Theoria 40:166-75, 1974.
J. McClelland & C. Chihara, "The Surprise Examination Paradox," J Phil Logic
 4:71-89, 1975.
C. Wright and A. Sudbury, "The Paradox of the Unexpected Examination,"
 Aust J Phil 55:41-58, 1977.
I. Kvart, "The Paradox of the Surprise Examination," Logique et Analyse
 337-344, 1978.
R. Sorenson, "Recalcitrant Versions of the Prediction Paradox," Aust J Phil
 69:355-62, 1982.
D. Olin, "The Prediction Paradox Resolved," Phil Stud 44:225-33, 1983.
R. Sorenson, "Conditional Blindspots and the Knowledge Squeeze: A Solution to
 the Prediction Paradox," Aust J Phil 62:126-35, 1984.
C. Chihara, "Olin, Quine and the Surprise Examination," Phil Stud 47:191-9,
 1985.
R. Kirkham, "The Two Paradoxes of the Unexpected Hanging," Phil Stud
 49:19-26, 1986.
D. Olin, "The Prediction Paradox: Resolving Recalcitrant Variations," Aust J
 Phil 64:181-9, 1986.
C. Janaway, "Knowing About Surprises: A Supposed Antinomy Revisited," Mind
 98:391-410, 1989.

    -- [e-mail].

==> logic/verger.p <==
A very bright and sunny Day
The Priest didst to the Verger say:
"Last Monday met I strangers three
None of which were known to Thee.
I ask'd Them of Their Age combin'd
which amounted twice to Thine!
A Riddle now will I give Thee:
Tell Me what Their Ages be!"

So the Verger ask'd the Priest:
"Give to Me a Clue at least!"
"Keep Thy Mind and Ears awake,
And see what Thou of this can make.
Their Ages multiplied make plenty,
Fifty and Ten Dozens Twenty."

The Verger had a sleepless Night
To try to get Their Ages right.
"I almost found the Answer right.
Please shed on it a little Light."
"A little Clue I give to Thee,
I'm older than all Strangers three."
After but a little While
The Verger answered with a Smile:
"Inside my Head has rung a Bell.
Now I know the answer well!"


Now, the question is:

How old is the PRIEST??
               ======

Xref: bloom-picayune.mit.edu rec.puzzles:18151 news.answers:3082
Newsgroups: rec.puzzles,news.answers
Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!sol.ctr.columbia.edu!destroyer!uunet!questrel!chris
From: uunet!questrel!chris (Chris Cole)
Subject: rec.puzzles FAQ, part 14 of 15
Message-ID: <[e-mail]>
Followup-To: rec.puzzles
Summary: This posting contains a list of
     Frequently Asked Questions (and their answers).
     It should be read by anyone who wishes to
     post to the rec.puzzles newsgroup.
Sender: [e-mail] (Chris Cole)
Reply-To: uunet!questrel!faql-comment
Organization: Questrel, Inc.
References: <[e-mail]>
Date: Mon, 21 Sep 1992 00:09:53 GMT
Approved: [e-mail]
Expires: Sat, 3 Apr 1993 00:08:21 GMT
Lines: 1574

Archive-name: puzzles-faq/part14
Last-modified: 1992/09/20
Version: 3

==> logic/verger.s <==
The puzzler tried to take the test;
Intriguing rhymes he wished to best.
But "Fifty and ten dozens twenty"
made his headache pound aplenty.
When he finally found some leisure,
He took to task this witty treasure.

"The product of the age must be
Twenty-Four Hundred Fifty!"
Knowing that, he took its primes,
permuted them as many times
as needed, til he found amounts
equal to, by all accounts,
twice the Verger's age, so that
He would have that next day's spat.

The reason for the lad's confusion
was due to multiple solution!
Hence he needed one more clue
to give the answer back to you!
Since only one could fit the bill,
and then confirm the priest's age still,
the eldest age of each solution
by one could differ, with no coercion.  <=(Sorry)

Else, that last clue's revelation
would not have brought information!
With two, two, five, seven, and seven,
construct three ages, another set of seven.
Two sets of three yield sixty-four,
Examine them, yet one time more.
The eldest age of each would be
forty-nine, and then, fifty!

With lack of proper rhyme and meter,
I've tried to be the first completor
of this poem and a puzzle;
my poetry, you'd try to muzzle!
And lest you think my wit is thrifty,
The answer, of course, must be fifty!
If dispute, you wish to tender,
note my addresss, as the sender!

--
Kevin Nechodom <[e-mail]>

==> logic/weighing/balance.p <==
You are given N balls and a balance scale and told that
one ball is slightly heavier or lighter than the other identical
ones.  The scale lets you put the same number of balls on each side
and observe which side (if either) is heavier.

1.     What's the minimum # of weighings X (and way of doing them)
that will always find the unique ball and whether it's heavy or light?

2.     If you are told the unique ball is, in fact, heavier than the
others, what's the minimum # of weighings Y to find it?

==> logic/weighing/balance.s <==
Martin Gardner gave a neat solution to this problem.

Assume that you are allowed N weighings.  Write down the 3^N possible
length N strings of the symbols '0', '1', and '2'.  Eliminate the three
such strings that consist of only one symbol repeated N times.

For each string, find the first symbol that is different from the symbol
preceeding it.  Consider that pair of symbols.  If that pair is not 01,
12, or 20, cross out that string.  In other words, we only allow strings
of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ).

You will have (3^N-3)/2 strings left.  This is how many balls you can
handle in N weighings.

Perform N weighings as follows:

    For weighing I, take all the balls that have a 0 in string
    position I, and weigh them against all the balls that have
    a 2 in string position I.

    If the side with the 0's in position I goes down, write down
    a 0.  If the other side goes down, write down a 2.  Otherwise,
    write down a 1.

After the N weighings, you have written down an N symbol string.  If
your string matches the string on one of the balls, then that is the
odd ball, and it is heavy.  If none of them match, than change every
2 to a 0 in your string, and every 0 to a 2.  You will then have a
string that matches one of the balls, and that ball is lighter than
the others.

Note that if you only have to identify the odd ball, but don't have to
determine if it is heavy or light, you can handle (3^N-3)/2+1 balls.
Label the extra ball with a string of all 1's, and use the above
method.

Note also that you can handle (3^N-3)/2+1 balls if you *do* have to
determine whether it is heavy or light, provided you have a single reference
ball available, which you know has the correct weight. You do this by
labelling the extra ball with a string of all 2s. This results in it being
placed on the same side of the scales each time, and in that side of the
scales having one more ball than the other each time. So you put the
reference ball on the other side of the scales to the "all 2s" ball on each
weighing.

Proving that this works is straightforward, once you notice that the
method of string construction makes sure that in each position, 1/3
of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a
string occurs, then the string obtained by replacing each 0 with a
2 and each 2 with a 0 does not occur.

==> logic/weighing/box.p <==
You have ten boxes; each contains nine balls.  The balls in one box
weigh 0.9 kg; the rest weigh 1.0 kg.  You have one weighing on a
scale to find the box containing the light balls.  How do you do it?

==> logic/weighing/box.s <==
Number the boxes 0-9.  Take 0 balls from box 0, 1 ball from box 1, 2
balls from box 2, etc.  Now weight all those balls and follow this
table:

If odd box is    Weight is
0        45 kg
1        44.9 kg
2        44.8 kg
3        44.7 kg
4        44.6 kg
5        44.5 kg
6        44.4 kg
7        44.3 kg
8        44.2 kg
9        44.1 kg

==> logic/weighing/gummy.bears.p <==
Real gummy drop bears have a mass of 10 grams, while imitation gummy
drop bears have a mass of 9 grams.  Spike has 7 cartons of gummy drop bears,
4 of which contain real gummy drop bears, the others imitation.
Using a scale only once and the minimum number of gummy drop bears, how
can Spike determine which cartons contain real gummy drop bears?

==> logic/weighing/gummy.bears.s <==
Spike used 51 gummy drop bears:  from the 7 boxes he took respectively
0, 1, 2, 4, 7, 13, and 24 bears.

The notion is that each box of imitation bears will subtract its
number of bears from the total "ideal" weight of 510 grams (1 gram of
missing weight per bear), so Spike weighs the bears, subtracts the
result from 510 to obtain a number N, and finds the unique combination
of 3 numbers from the above list (since there are 3 "imitation" boxes)
that sum to N.

The trick is for the sums of all triples selected from the set S of
numbers of bears to be unique.  To accomplish this, I put numbers into
S one at a time in ascending order, starting with the obvious choice,
0.  (Why is this obvious?  If I'd started with k > 0, then I could
have improved on the resulting solution by subtracting k from each
number) Each new number obviously had to be greater than any previous,
because otherwise sums are not unique, but also the sums it made when
paired with any previous number had to be distinct from all previous
pairs (otherwise when this pair is combined with a third number you
can't distinguish it from the other pair)--except for the last box,
where we can ignore this point.  And most obviously all the new
triples had to be distinct from any old triples; it was easy to find
what the new triples were by adding the newest number to each old sum
of pairs.

Now, in case you're curious, the possible weight deficits and their
unique decompositions are:

3       = 0 + 1 + 2
5       = 0 + 1 + 4
6       = 0 + 2 + 4
7       = 1 + 2 + 4
8       = 0 + 1 + 7
9       = 0 + 2 + 7
10      = 1 + 2 + 7
11      = 0 + 4 + 7
12      = 1 + 4 + 7
13      = 2 + 4 + 7
14      = 0 + 1 + 13
15      = 0 + 2 + 13
16      = 1 + 2 + 13
17      = 0 + 4 + 13
18      = 1 + 4 + 13
19      = 2 + 4 + 13
20      = 0 + 7 + 13
21      = 1 + 7 + 13
22      = 2 + 7 + 13
24      = 4 + 7 + 13
25      = 0 + 1 + 24
26      = 0 + 2 + 24
27      = 1 + 2 + 24
28      = 0 + 4 + 24
29      = 1 + 4 + 24
30      = 2 + 4 + 24
31      = 0 + 7 + 24
32      = 1 + 7 + 24
33      = 2 + 7 + 24
35      = 4 + 7 + 24
37      = 0 + 13 + 24
38      = 1 + 13 + 24
39      = 2 + 13 + 24
41      = 4 + 13 + 24
44      = 7 + 13 + 24

Note that there had to be (7 choose 3) distinct values; they end up
ranging from 3 to 44 inclusive with 7 numbers missing:  4, 23, 34, 36,
40, 42, and 43.

-- David Karr ([e-mail])

==> logic/weighing/weighings.p <==
Some of the supervisors of Scandalvania's n mints are producing bogus coins.
It would be easy to determine which mints are producing bogus coins but,
alas, the only scale in the known world is located in Nastyville,
which isn't on very friendly terms with Scandalville.  In fact, Nastyville's
king will only let you use the scale twice.  Your job?  You must determine
which of the n mints are producing the bogus coins using only two weighings
and the minimum number of coins (your king is rather parsimonious, to put it
nicely).  This is a true scale, i.e. it will tell you the weight of whatever
you put on it.  Good coins are known to have a weight of 1 ounce and it is
also known that all the bogus mints (if any) produce coins that are
light or heavy by the same amount.

Some examples: if n=1 then we only need 1 coin, if n=2 then clearly 2
coins suffice, one from each mint.

What are the solutions for n=3,4,5?  What can be said for general n?

==> logic/weighing/weighings.s <==
Oh gracious and wise king, I have solved this problem by first
simplifying and then expanding.  That is, consider the problem of
being allowed only a single weighing.  Stop reading right now if you
want to think about it further.

There are three possible outcomes for each mint (light, OK, heavy)
which may be represented as (-1, 0, +1).  Now, let each mint represent
one place in base 3.  Thus, the first mint is the ones place, the
second the threes place, the third is the nines place and so on.  The
number of coins from each mint must equal the place.  That is, we'll
have 1 coin from mint 1, 3 from mint 2, 9 from mint 3, and, in
general, 3^(n-1) from mint n.

By weighing all coins at once, we will get a value between 1 + 3 + 9 +
...  and -1 + -3 + -9 + ...  In fact, we notice that that value will
be unique for any mint outcomes.  Thus, for the one weighing problem,
we need

sum for i=1 to n (3^(i-1))

which evaluates to (3^n - 1)/2

I'm fairly satisfied that this is a minimum for a single weighing.
What does a second weighing give us?  Well, we can divide the coins
into two groups and use the same method.  That is, if we have 5 mints,
one weighing will be:

1 coin from mint 1 + 3 coins from mint 2 + 9 coins from mint 3

while the other weighing will be:

1 coin from mint 4 + 3 coins from mint 5

It's pretty plain that this gives us a total coinage of:

   3^(n/2) - 1 for even n and, after some arithmetic agitation:
   2 * 3^((n-1)/2) - 1 for odd n

I think the flaw in this solution is that we don't know ahead of time
the amount by which the coins are off weight.  So if you weigh 1 coin
from mint 1 together with 3 coins from mint 2 and the result is heavy
by 3x units, you still don't know whether the bogus coins are from
mint 3 (heavy by x units) or from mint 1 (heavy by 3x units).  Note
that we're not given the error amount, only the fact that is is equal
for all bogus coins.

Here is my partial solution:

After considering the above, it would seem that on each of the two
weighings we must include coins from all of the mints (except for the
special cases of small n).  So let ai (a sub i) be the number of coins
from mint i on weighing 1 and bi be the number of coins from mint i on
weighing 2.  Let the error in the bogus coins have a value x, and let
ci be a the counterfeit function: ci is 0 if mint i is good, 1
otherwise.